1. Field of the Invention
This invention relates to computer and network systems and, more particularly, to routing packets within a computer or network system.
2. Description of the Related Art
Generally, personal computers (PCs) and other types of computer systems have been designed around a shared bus system for accessing memory. Thus, one or more processors and one or more input/output (I/O) devices are typically coupled to memory through a shared bus. The I/O devices may be coupled to the shared bus through an I/O bridge that manages the transfer of information between the shared bus and the I/O devices, and processors are typically coupled directly to the shared bus or are coupled through a cache hierarchy to the shared bus.
Unfortunately, shared bus systems may experience several drawbacks. For example, since there are multiple devices attached to the shared bus, the bus is typically operated at a relatively low frequency. The multiple attachments present a high capacitive load to a device driving a signal on the bus, and the multiple attachment points present a relatively complicated transmission line model for high frequencies. Accordingly, the frequency remains low, and thus the bandwidth available on the shared bus is relatively low. The low bandwidth presents a barrier to attaching additional devices to the shared bus, since additional devices may negatively impact performance.
Another disadvantage of the shared bus system is a lack of scalability to larger numbers of devices. As mentioned above, the amount of bandwidth is fixed (and may decrease if adding additional devices reduces the operable frequency of the bus). Once the bandwidth requirements of the devices attached to the bus (either directly or indirectly) exceeds the available bandwidth of the bus, devices will frequently be stalled when attempting access to the bus. As a result, overall performance may be decreased.
One or more of the above problems may be addressed by using a distributed memory system. A computer system employing a distributed memory system includes multiple nodes. Two or more of the nodes are connected to memory, and the nodes are interconnected using any suitable interconnect. For example, each node may be connected to each other node using dedicated communication lines. Alternatively, each node may connect to a fixed number of other nodes, and transactions may be routed from a first node to a second node to which the first node is not directly connected via one or more intermediate nodes. The memory address space is assigned across the memories in each node.
Generally, a “node” is a device which is capable of participating in transactions upon the interconnect. For example, in a packet-based interconnect the node may be configured to receive and transmit packets to other nodes. One or more packets may be employed to perform a particular transaction. A particular node may be a destination for a packet, in which case the information is accepted by the node and processed internally in the node. Alternatively, the particular node may be used to relay a packet from a source node to a destination node if the particular node is not the destination node of the packet.
Distributed memory systems present design challenges that differ from the challenges in shared bus systems. For example, shared bus systems regulate the initiation of transactions through bus arbitration. Accordingly, a fair arbitration algorithm allows each bus participant the opportunity to initiate transactions. The order of transactions on the bus may represent the order that transactions are performed (e.g., for coherency purposes). On the other hand, in distributed memory systems, nodes may initiate transactions concurrently and use the interconnect to transmit the transactions to other nodes. These transactions may have logical conflicts between them (e.g., coherency conflicts for transactions to the same address) and may experience resource conflicts (e.g., buffer space may not be available in various nodes) since no central mechanism for regulating the initiation of transactions is provided. Accordingly, it is more difficult to ensure that information continues to propagate among the nodes smoothly and that deadlock situations (in which no transactions are completed due to conflicts between the transactions) are avoided.
By employing virtual channels and allocating different resources to the virtual channels, conflicts may be reduced. A “virtual channel” is a communication path for initiating transactions (e.g., by transmitting packets containing commands) between various processing nodes. Each virtual channel may be resource-independent of the other virtual channels (i.e., packets flowing in one virtual channel are generally not affected, in terms of physical transmission, by the presence or absence of packets in another virtual channel). Packets that do not have logical/protocol-related conflicts may be grouped into a virtual channel. For example, packets may be assigned to a virtual channel based upon packet type. Packets in the same virtual channel may physically conflict with each other's transmission (i.e., packets in the same virtual channel may experience resource conflicts), but may not physically conflict with the transmission of packets in a different virtual channel (by virtue of the virtual channels being resource-independent of each other). Accordingly, logical conflicts occur between packets in separate virtual channels. Since packets that may experience resource conflicts do not experience logical conflicts and packets which may experience logical conflicts do not experience resource conflicts, deadlock-free operation may be achieved.
One problem that may arise in a packet-based system occurs when buffers are used to temporarily store packets received by a node before outputting the packets from the node. Typically, packets are allocated to each of the node's interfaces and each of the virtual channels. However, each interface's and each virtual channel's usage of the buffers may vary over time. Thus, certain interfaces and/or virtual channels may experience less than optimal performance at times when those interfaces and virtual channels are experiencing heavy traffic. Likewise, buffer capacity may be underutilized if traffic is relatively low for other interfaces and virtual channels. Accordingly, it is desirable to be able to more efficiently utilize buffers within a node.